<!--
 * @Author: your name
 * @Date: 2021-04-11 22:21:36
 * @LastEditTime: 2021-04-11 23:12:28
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \JavaScript\08 - 数组排序.html
-->
<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>Document</title>
</head>
<body>
  <script>
    let arr = [10, 9, 12, 16, 7]

    // 1.冒泡法
    // 拿出某一项，让后面的每一项都跟这项比较，若后面的小，则交换位置
    // for (let i = 0; i < arr.length -1; i++) {
    //   const cur = arr[i]
    //   for (let j = i + 1; j < arr.length; j ++) { // 从后一项开始比较
    //     const next = arr[j]
    //     if (cur > next) {
    //       [arr[i], arr[j]] = [arr[j], arr[i]] // 使用ES6的解构赋值交换位置
    //     }
    //   }
    // }

    // 2.插入排序(比喻为斗地主)
    // 1.准备一个新数组，用来存储抓到手里的牌，开始先抓一张牌进来
    // let newArr = [arr[0]]
    // // 2.从第二项开始依次抓牌，一直到把台面上的牌抓光
    // for (let i = 1; i < arr.length; i++) {
    //   // next是新抓的牌
    //   const next = arr[i]
    //   // 和newArr手里的牌依次比较（从后向前比）
    //   for (let j = newArr.length - 1; j >= 0; j--) { //从后往前比
    //     // 每一次要比较的手里的牌
    //     const cur = arr[j]
    //     // 如果当前新牌next比要比较的牌cur大了，把next放到cur的后面
    //     if (next > cur) {
    //       newArr.push(next)
    //       // newArr.splice(j+1, 0, next)
    //       break
    //     }
    //     // 已经比到第一项，我们把新牌放到手中最前面即可
    //     if (j === 0) {
    //       newArr.unshift(next)
    //     }
    //   }
    // }
    // console.log(newArr); // [7, 9, 10, 12, 16]

    // 3.快速定位法（二分法）
    function quick(arr) {
      if (arr.length <= 1) return arr;
      // 找到中间项
      const middleIdx = Math.floor(arr.length/2)
      const middleItem = arr[middleIdx]
      let [leftArr, rightArr] = [[], []]
      for (let i = 0; i < arr.length; i++) {
        const cur = arr[i]
        if (cur > middleItem) {
          rightArr.push(cur)
        } else if (cur < middleItem) {
          leftArr.push(cur)
        }
      }
      return [...quick(leftArr), middleItem, ...quick(rightArr)]
    }
    console.log(quick(arr));
    
  </script>
</body>
</html>